//
// Created by yanhai on 2021/1/10.
//

/**
 * 单向链表操作
 */

#ifndef __LINK_COMMON_H__
#define __LINK_COMMON_H__

#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int KEY_TYPE;

typedef struct link_node_ {
    KEY_TYPE key;
    struct link_node_ *next;
} link_node;

typedef struct link_ {
    link_node *root;
} link;

/**
 * 将节点插入链表头部
 * @param T
 * @param node
 * @return
 */
int link_insert(link *T, link_node *node)
{
    node->next = T->root;
    T->root = node;
    return 0;
}

/**
 * 将节点插入链表尾部
 * @param T
 * @param node
 * @return
 */
int link_append(link *T, link_node *node)
{
    if (T->root == NULL) {
        T->root = node;
    } else {
        link_node *t = T->root;
        while (t->next != NULL) {
            t = t->next;
        }
        t->next = node;
    }
    return 0;
}

/**
 * 查找节点
 * @param T
 * @param key
 * @return
 */
link_node *link_find(link *T, KEY_TYPE key)
{
    link_node *t = T->root;
    while (t != NULL) {
        if (t->key == key) {
            return t;
        }
        t = t->next;
    }
    return NULL;
}

/**
 * 打印链表
 * @param T
 */
void link_print(const link *T)
{
    link_node *t = T->root;
    while (t != NULL) {
        printf("%4d", t->key);
        t = t->next;
    }
    printf("\n");
}

/**
 * 销毁一个链表
 * @param T
 */
void link_destroy(link *T)
{
    link_node *node;
    while (T->root != NULL) {
        node = T->root;
        T->root = node->next;
//        printf("free %p\n", node);
        free(node);
    }

    T->root = NULL;
}

/**
 * 创建node节点
 * @param key
 * @return
 */
link_node *link_node_create(KEY_TYPE key)
{
    link_node *node = (link_node *) malloc(sizeof(link_node));
    assert(node != NULL);
//    printf("malloc %p\n", node);

    node->key = key;
    node->next = NULL;
    return node;
}

/**
 * 生成一个链表
 * @param length 链表长度
 * @param reverse 是否逆序
 * @return
 */
link link_create_from_index(int length, bool reverse)
{
    link T;
    T.root = NULL;

    for (int i = 0; i < length; i++) {
        link_node *node = link_node_create(i);

        if (reverse) {
            link_insert(&T, node);
        } else {
            link_append(&T, node);
        }
    }

    return T;
}

/**
 * 根据一个数组，创建一个链表
 * @param a 数组
 * @param length 数组长度
 * @param reverse 是否逆序
 * @return
 */
link link_create_from_array(const KEY_TYPE *a, int length, bool reverse)
{
    link T;
    T.root = NULL;

    for (int i = 0; i < length; i++) {
        link_node *node = link_node_create(a[i]);

        if (reverse) {
            link_insert(&T, node);
        } else {
            link_append(&T, node);
        }
    }

    return T;
}

#endif //__LINK_COMMON_H__
